/**
 * 
 */
package util;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

import algoritmos.Kruskal;

import modelo.Aresta;
import modelo.Grafo;
import modelo.Vertice;

/**
 * @author Rogerio
 *
 */
public class Gerador {
//	private	ArrayList<Grafo> grafos;
	
	public Gerador() {
//		this.grafos = new ArrayList<Grafo>();
	}
	
	/**
	 * Gerador de grafos completos
	 * 
	 * @param totalVertices
	 * @return
	 */
	public ArrayList<Grafo> geraGrafosCompletos(int totalVertices){
		ArrayList<Grafo> grafos = new ArrayList<Grafo>();
		
		//Gerando as n*n(-1)/2 arestas
		for(int i = 0; i< 10;i++){ //variando de 0 a 9 para criar as 10 inst�ncias
			//System.out.println("gerei instancia" + i);
			
			//Conjunto de Vertices para adicionar no Grafo
			List<Vertice> listaVertices = new ArrayList<Vertice>();
			
			//Gerando todos os n v�rtices
			for(int y = 0; y< totalVertices;y++){
				listaVertices.add(new Vertice("v"+y));
			}
			
			//Conjunto de Arestar para adicionar no Grafo
			Set<Aresta> listaArestas = new HashSet<Aresta>();
			
			//Gerando um grafo atual
			for(int j = 0; j< listaVertices.size(); j++){ //iterar sobre a lista de V�rtices -> Origem
				//System.out.println("j: "+j);
				for(int w = j+1; w< listaVertices.size(); w++){ // iterar sobre a lista de V�rtices -> Destino
					Vertice vertice = listaVertices.get(j);
					Vertice verticeAux = listaVertices.get(w);
					
					//Gerando os pesos aleatoriamente
					int peso = geradorPesoAleatorio();
					
					//Criando as duas arestas, ida e volta
					Aresta novaArestaOrigem = new Aresta(vertice, verticeAux, peso);
					Aresta novaArestaDestino = new Aresta(verticeAux,vertice, peso);
					
					//adicionar as arestas no grafo
					listaArestas.add(novaArestaOrigem);
					//listaArestas.add(novaArestaDestino);
					
					//adicionar as arestas nos v�rtices, ida e volta
					vertice.getArestasAdj().add(novaArestaOrigem);
					verticeAux.getArestasAdj().add(novaArestaDestino);
					
				}
			}
			//Adicionando o novo grafo na lista
			//System.out.println("Add Grafo");
			grafos.add(new Grafo(listaVertices,listaArestas));
		}
		return grafos;
	}
	
	/**
	 * 
	 * @param totalVertices
	 * @param fatorK
	 * @return
	 */
	public ArrayList<Grafo> geraGrafosNaoCompletos(int totalVertices, int fatorK){
		//garantir que o fator nao seja muito grande
		int totalDeArestas = totalVertices*fatorK;
		int maxArestas = (totalVertices*(totalVertices-1))/2;
		if(totalDeArestas > maxArestas){
			totalDeArestas = maxArestas;
		}
		
		ArrayList<Grafo> grafos = new ArrayList<Grafo>();
		
		//La�o para gerar todas as 10 inst�ncias
		while(grafos.size() < 10){
			
			//Conjunto de Vertices para adicionar no Grafo
			List<Vertice> listaVertices = new ArrayList<Vertice>();
			
			//Gerando todos os n v�rtices
			for(int y = 0; y< totalVertices;y++){
				listaVertices.add(new Vertice("v"+y));
			}
			
			//Conjunto de Arestar para adicionar no Grafo
			Set<Aresta> listaArestas = new HashSet<Aresta>();			
			
			//Gerando o grafo atual
			while(listaArestas.size()<totalDeArestas){
				
				//Uso o m�todo para gerar um v�rtice aleat�rio
				Vertice v1 = listaVertices.get(geraVerticeAleatorio(listaVertices.size()));
				Vertice v2 = listaVertices.get(geraVerticeAleatorio(listaVertices.size()));
				
				//Mas testo se ambos s�o iguais -> evita ciclos
				if(!v1.equals(v2)){
					int peso = geradorPesoAleatorio();
					Aresta novaArestaOrigem = new Aresta(v1, v2, peso);
					Aresta novaArestaDestino = new Aresta(v2,v1, peso);
					//evitar arestas paralelas
					boolean contains = false;
					for (Aresta a : listaArestas) {
						contains = contains || a.equals(novaArestaOrigem);
					}
					if(!contains){
						listaArestas.add(novaArestaOrigem);
						//listaArestas.add(novaArestaDestino);
						v1.getArestasAdj().add(novaArestaOrigem);
						v2.getArestasAdj().add(novaArestaDestino);
						//System.out.println("add: "+novaArestaOrigem.getOrigem()+" -> "+novaArestaOrigem.getDestino());
					}else{
						//System.out.println("ja tem: "+novaArestaOrigem.getOrigem()+" -> "+novaArestaOrigem.getDestino());
					}
				}
			}
			//System.out.println("qtd arestas: "+listaArestas.size());
			Grafo newGrafo = new Grafo(listaVertices,listaArestas); 
			if(isConectado(newGrafo)){
				//System.out.println("Add Grafo");
				grafos.add(newGrafo);
			}
		}
		return grafos;
	}
	/**
	 * Gerador de Pesos aleat�rio
	 * 
	 * @return um valor inteiro no limite do m�todo
	 */
	public int geradorPesoAleatorio(){
		Random r = new Random();
		return r.nextInt(10000);
	}
	
	/**
	 * M�todo utilizado para gerar um inteiro que ser� utilizado para escolher um v�rtice aleatoriamente
	 * no m�todo de gera��o de grafos parciais.
	 *  
	 * @param n
	 * @return um inteiro dentro dos limites dos v�rtices
	 */
	private int geraVerticeAleatorio(int n){
		Random r = new Random();
		return r.nextInt(n);
	}
	
	
	private boolean isConectado(Grafo grafo){
		return Kruskal.kruskal(grafo);
	}
	
}
